package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;

/**
 * @author: xiaomi
 * @date: 2021/3/9
 * @description: 1047. 删除字符串中的所有相邻重复项
 * https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
 */
public class A_1047_删除字符串中的所有相邻重复项 {

	static A_1047_删除字符串中的所有相邻重复项 action = new A_1047_删除字符串中的所有相邻重复项();

	public static void main(String[] args) {
		test1();
		test2();
	}

	public static void test1() {
		// 5
		String s = "abbaca";
		String res = action.removeDuplicatesByStack(s);
		System.out.println("res = " + res);
	}

	public static void test2() {
		// 5
		String s = "ibfjcaffccadidiaidchakchchcahabhibdcejkdkfbaeeaecdjhajbkfebebfea";
		String res = action.removeDuplicatesFail(s);
		System.out.println("res = " + res);
	}


	/**
	 * 尝试使用双指针解决
	 * 这个方案通过不了 test2
	 * 因为：
	 * caffcca
	 * 这种情况无法快速解决！
	 * --
	 * 考虑使用 栈来实现：
	 * 1.即时清除重复元素；
	 * 2.上一个是否需要被清除由下一个决定！
	 *
	 * @param S
	 * @return
	 */
	public String removeDuplicatesFail(String S) {
		char[] chars = S.toCharArray();
		int len = chars.length;
		if (len < 2) {
			return S;
		}
		int[] recordArr = new int[len];
		int begin = 0, end = 1;
		while (end < len) {
			if (chars[begin] == chars[end]) {
				recordArr[begin] = 1;
				recordArr[end] = 1;


				if (begin == 0 || recordArr[begin - 1] == 1) {
					begin = end + 1;
					end = begin + 1;
				} else {
					begin--;
					end++;
				}
			} else {
				begin = end;
				end++;
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < len; i++) {
			if (recordArr[i] == 0) {
				sb.append(chars[i]);
			}
		}
		return sb.toString();
	}

	/**
	 * 通过栈来实现
	 *
	 * @param S
	 * @return
	 */
	public String removeDuplicatesByStack(String S) {
		char[] chars = S.toCharArray();
		int len = chars.length;
		if (len < 2) {
			return S;
		}
		ArrayDeque<Character> deque = new ArrayDeque<>(len);
		deque.addLast(chars[0]);
		int index = 1;
		while (index < len) {
			if (deque.isEmpty()){
				deque.addLast(chars[index]);
			}else {
				if (deque.peekLast() == chars[index]) {
					deque.removeLast();
				}else {
					deque.addLast(chars[index]);
				}
			}

			index++;
		}
		StringBuilder sb = new StringBuilder();
		while (!deque.isEmpty()){
			sb.append(deque.removeFirst());
		}
		return sb.toString();
	}
}
